package problems.practice;

import java.util.ArrayList;
import java.util.List;

/**
 * 438. 找到字符串中所有字母异位词
 * https://leetcode.cn/problems/find-all-anagrams-in-a-string/
 *
 * @author habitplus
 * @since 2022/8/13 17:19
 */
public class T438 {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<>();
        if (s == null
                || s.length() < 1
                || p == null
                || p.length() < 1
                || s.length() < p.length()) return ret;
        int[] m = new int[26];
        int len = p.length();
        for (char c : p.toCharArray()) m[c - 'a']++;

        int[] countMap = new int[26];
        char[] chs = s.toCharArray();
        int n = chs.length;
        int index;

        for (int i = 1; i <= n; ++i) {
            index = chs[i - 1] - 'a';
            countMap[index]++;
            if (i >= len) {
                if (equal(m, countMap))
                    ret.add(i - len);
                countMap[chs[i - len] - 'a']--;
            }
        }
        return ret;
    }

    private boolean equal(int[] arr1, int[] arr2) {
        int n = arr1.length;
        int i = 0;
        while (i < n && arr1[i] == arr2[i]) ++i;
        return i == n;
    }
}
